|
In mathematics, a Tamari lattice, introduced by , is a partially ordered set in which the elements consist of different ways of grouping a sequence of objects into pairs using parentheses; for instance, for a sequence of four objects ''abcd'', the five possible groupings are ((''ab'')''c'')''d'', (''ab'')(''cd''), (''a''(''bc''))''d'', ''a''((''bc'')''d''), and ''a''(''b''(''cd'')). Each grouping describes a different order in which the objects may be combined by a binary operation; in the Tamari lattice, one grouping is ordered before another if the second grouping may be obtained from the first by only rightward applications of the associative law (''xy'')''z'' = ''x''(''yz''). For instance, applying this law with ''x'' = ''a'', ''y'' = ''bc'', and ''z'' = ''d'' gives the expansion (''a''(''bc''))''d'' = ''a''((''bc'')''d''), so in the ordering of the Tamari lattice (''a''(''bc''))''d'' ≤ ''a''((''bc'')''d''). In this partial order, any two groupings ''g''1 and ''g''2 have a greatest common predecessor, the ''meet'' ''g''1 ∧ ''g''2, and a least common successor, the ''join'' ''g''1 ∨ ''g''2. Thus, the Tamari lattice has the structure of a lattice. The Hasse diagram of this lattice is isomorphic to the graph of vertices and edges of an associahedron. The number of elements in a Tamari lattice for a sequence of ''n'' + 1 objects is the ''n''th Catalan number. The Tamari lattice can also be described in several other equivalent ways: *It is the poset of sequences of ''n'' integers ''a''1, ..., ''a''''n'', ordered coordinatewise, such that ''i'' ≤ ''a''''i'' ≤ ''n'' and if ''i'' ≤ ''j'' ≤ ''a''''i'' then ''a''''j'' ≤ ''a''''i'' . *It is the poset of binary trees with ''n'' leaves, ordered by tree rotation operations. *It is the poset of ordered forests, in which one forest is earlier than another in the partial order if, for every ''j'', the ''j''th node in a preorder traversal of the first forest has at least as many descendants as the ''j''th node in a preorder traversal of the second forest . *It is the poset of triangulations of a convex ''n''-gon, ordered by flip operations that substitute one diagonal of the polygon for another. ==Notation== The Tamari lattice of the C''n'' groupings of ''n''+1 objects is called T''n'', but the corresponding associahedron is called K''n''+1. In ''The Art of Computer Programming'' T4 is called the ''Tamari lattice of order 4'' and its Hasse diagram K5 the ''associahedron of order 4''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Tamari lattice」の詳細全文を読む スポンサード リンク
|